{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Satisfiability of Equality Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equationsPossible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等式方程的可满足性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 <code>equations[i]</code> 的长度为 <code>4</code>，并采用两种不同的形式之一：<code>&quot;a==b&quot;</code> 或&nbsp;<code>&quot;a!=b&quot;</code>。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。</p>\n",
    "\n",
    "<p>只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回&nbsp;<code>true</code>，否则返回 <code>false</code>。&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[&quot;a==b&quot;,&quot;b!=a&quot;]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[&quot;b==a&quot;,&quot;a==b&quot;]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[&quot;a==b&quot;,&quot;b==c&quot;,&quot;a==c&quot;]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[&quot;a==b&quot;,&quot;b!=c&quot;,&quot;c==a&quot;]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[&quot;c==c&quot;,&quot;b==d&quot;,&quot;x!=z&quot;]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= equations.length &lt;= 500</code></li>\n",
    "\t<li><code>equations[i].length == 4</code></li>\n",
    "\t<li><code>equations[i][0]</code> 和&nbsp;<code>equations[i][3]</code>&nbsp;是小写字母</li>\n",
    "\t<li><code>equations[i][1]</code> 要么是&nbsp;<code>&#39;=&#39;</code>，要么是&nbsp;<code>&#39;!&#39;</code></li>\n",
    "\t<li><code>equations[i][2]</code>&nbsp;是&nbsp;<code>&#39;=&#39;</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [satisfiability-of-equality-equations](https://leetcode.cn/problems/satisfiability-of-equality-equations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [satisfiability-of-equality-equations](https://leetcode.cn/problems/satisfiability-of-equality-equations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"a==b\",\"b!=a\"]', '[\"b==a\",\"a==b\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        p = {}\n",
    "        for e in equations:\n",
    "            a, b = e[0], e[-1]\n",
    "            p[a] = a\n",
    "            p[b] = b\n",
    "        def find(a):\n",
    "            if p[a] != a:\n",
    "                p[a] = find(p[a])\n",
    "            return p[a]\n",
    "        r = defaultdict(int)\n",
    "        def union(a, b):\n",
    "            pa = find(a)\n",
    "            pb = find(b)\n",
    "            if r[pa] < r[pb]:\n",
    "                p[pa] = pb\n",
    "            elif r[pb] < r[pa]:\n",
    "                p[pb] = pa\n",
    "            else:\n",
    "                p[pa] = pb\n",
    "                r[pb] += 1\n",
    "        for e in equations:\n",
    "            a, s, b = e[0], e[1], e[-1]\n",
    "            if s == '=' and a != b:\n",
    "                union(a, b)\n",
    "        for e in equations:\n",
    "            a, s, b = e[0], e[1], e[-1]\n",
    "            if s == '!' and find(a) == find(b):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: 'List[str]') -> 'bool':\n",
    "        pre = {}\n",
    "        test = []\n",
    "        def find(a):\n",
    "            if a in pre:\n",
    "                return find(pre[a])\n",
    "            else:\n",
    "                return a\n",
    "        \n",
    "        for i in equations:\n",
    "            if i[1] == '=':\n",
    "                root_a = find(i[0])\n",
    "                root_b = find(i[3])\n",
    "                if root_a != root_b:\n",
    "                    pre[root_a] = root_b\n",
    "            else:\n",
    "                test.append((i[0], i[3]))\n",
    "        for i in test:\n",
    "            if find(i[0]) == find(i[1]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: 'List[str]') -> 'bool':\n",
    "        tmp = {chr(i): chr(i) for i in range(97, 125)}\n",
    "        \n",
    "        def find(x):\n",
    "            if x != tmp[x]:\n",
    "                tmp[x]= find(tmp[x])\n",
    "            return tmp[x]\n",
    "        \n",
    "        for it in equations:\n",
    "            if it[1] == '=':\n",
    "                tmp[find(it[0])] = find(it[-1])\n",
    "                \n",
    "        for it in equations:\n",
    "            if it[1] == '!':\n",
    "                if find(it[0]) == find(it[-1]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: 'List[str]') -> 'bool':\n",
    "        dic = {}\n",
    "\n",
    "        def in_dic(node, x, s=None):\n",
    "            if s is None:\n",
    "                s = set()\n",
    "            if b in dic[node]:\n",
    "                return True\n",
    "            for a in dic[node]:\n",
    "                if a not in s:\n",
    "                    s.add(a)\n",
    "                    if in_dic(a, x, s):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for e in equations:\n",
    "            if e[1] == '=':\n",
    "                a = e[0]\n",
    "                b = e[3]\n",
    "                if a == b:\n",
    "                    continue\n",
    "                if dic.get(a) is None:\n",
    "                    dic[a] = set()\n",
    "                if dic.get(b) is None:\n",
    "                    dic[b] = set()\n",
    "                dic[a].add(b)\n",
    "                dic[b].add(a)\n",
    "\n",
    "        print(dic)\n",
    "\n",
    "        for e in equations:\n",
    "            if e[1] == '!':\n",
    "                a = e[0]\n",
    "                b = e[3]\n",
    "                if a == b:\n",
    "                    return False\n",
    "                if dic.get(a) is None or dic.get(b) is None:\n",
    "                    continue\n",
    "                print(a, b)\n",
    "                if in_dic(a, b):\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: 'List[str]') -> 'bool':\n",
    "\n",
    "        def dfs(current_num, current_set: 'set', type, has_used):\n",
    "            current_set.add(current_num)\n",
    "            print(current_num)\n",
    "            has_used.add(current_num)\n",
    "            for i in range(total_alpha):\n",
    "                if buf[current_num][i] == type and i not in current_set:\n",
    "                    dfs(i, current_set, type, has_used)\n",
    "\n",
    "        total_alpha = 26\n",
    "        buf = [[0 for j in range(total_alpha)] for i in range(total_alpha)]\n",
    "        for i in range(total_alpha):\n",
    "            buf[i][i] = 1\n",
    "        for equation in equations:\n",
    "            char1 = ord(equation[0]) - ord('a')\n",
    "            char2 = ord(equation[3]) - ord('a')\n",
    "            if equation[1] == '!':\n",
    "                if buf[char1][char2] == 1:\n",
    "                    return False\n",
    "                buf[char1][char2] = -1\n",
    "                buf[char2][char1] = -1\n",
    "            if equation[1] == '=':\n",
    "                if buf[char1][char2] == -1:\n",
    "                    return False\n",
    "                buf[char1][char2] = 1\n",
    "                buf[char2][char1] = 1\n",
    "\n",
    "        has_used = set()\n",
    "        for i in range(total_alpha):\n",
    "            if i not in has_used:\n",
    "                current_set = set()\n",
    "                dfs(i, current_set, 1, has_used)\n",
    "                current_list = list(current_set)\n",
    "                for j in range(len(current_list)):\n",
    "                    for k in range(j + 1, len(current_list)):\n",
    "                        if buf[current_list[j]][current_list[k]] == -1:\n",
    "                            print(j,k)\n",
    "                            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: 'List[str]') -> 'bool':\n",
    "        h = {}\n",
    "        def search(c):\n",
    "            while h.get(c,c) != c:\n",
    "                c = h[c]\n",
    "            return c\n",
    "        for e in equations:\n",
    "            if e[1] == \"=\":\n",
    "                if e[0] not in h:\n",
    "                    h[e[0]] = e[0]\n",
    "                h[search(e[3])] = search(e[0])\n",
    "        for e in equations:\n",
    "            if e[1] == \"!\":\n",
    "                if search(e[0]) == search(e[3]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        parent = [i for i in range(26)]\n",
    "        for eqn in equations:\n",
    "            if eqn[1] == '=':\n",
    "                x = ord(eqn[0]) - ord('a')\n",
    "                y = ord(eqn[3]) - ord('a')\n",
    "                self.union(parent, x, y)\n",
    "        for eqn in equations:\n",
    "            if eqn[1] == '!':\n",
    "                x = ord(eqn[0]) - ord('a')\n",
    "                y = ord(eqn[3]) - ord('a')\n",
    "                if self.find(parent, x)==self.find(parent, y):\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "    def find(self, parent, i):\n",
    "        if parent[i] != i:\n",
    "            parent[i] = self.find(parent, parent[i])\n",
    "        return parent[i]\n",
    "    \n",
    "    def union(self, parent, x, y):\n",
    "        x_set = self.find(parent, x)\n",
    "        y_set = self.find(parent, y)\n",
    "        if x_set != y_set:\n",
    "            parent[y_set] = x_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, char):\n",
    "        self.char = char\n",
    "        self.p = None\n",
    "        self.node_num = 1\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        # 取等于号的，形成几个团\n",
    "        # 再取不等号，看看有没矛盾\n",
    "        # 并查集\n",
    "        def findRoot(node):\n",
    "            while node.p:\n",
    "                node = node.p\n",
    "            return node\n",
    "\n",
    "        unequals = []\n",
    "        dsu = {}\n",
    "        for equation in equations:\n",
    "            if equation[1] == '!':\n",
    "                if equation[0] == equation[3]:\n",
    "                    return False\n",
    "                else:\n",
    "                    unequals.append(equation)\n",
    "            else:\n",
    "                char1 = equation[0]\n",
    "                char2 = equation[3]\n",
    "                if char1 not in dsu:\n",
    "                    dsu[char1] = DSU(char1)\n",
    "                if char2 not in dsu:\n",
    "                    dsu[char2] = DSU(char2)\n",
    "                r1 = findRoot(dsu[char1])\n",
    "                r2 = findRoot(dsu[char2])\n",
    "                if r1 == r2:\n",
    "                    continue\n",
    "                if r1.node_num >= r2.node_num:\n",
    "                    r2.p = r1\n",
    "                    r1.node_num += r2.node_num\n",
    "                else:\n",
    "                    r1.p = r2\n",
    "                    r2.node_num += r1.node_num\n",
    "        print(dsu)\n",
    "        for unequal in unequals:\n",
    "            if unequal[0] not in dsu or unequal[3] not in dsu:\n",
    "                continue\n",
    "            r1 = findRoot(dsu[unequal[0]])\n",
    "            r2 = findRoot(dsu[unequal[3]])\n",
    "            if r1 == r2:\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        graph = [[] for i in range(26)]\n",
    "        for i in equations:\n",
    "            if i[1]=='=':\n",
    "                x=ord(i[0])-ord('a')\n",
    "                y = ord(i[3])-ord('a')\n",
    "                graph[x].append(y)\n",
    "                graph[y].append(x)\n",
    "        color=[None]*26\n",
    "        t=0\n",
    "        for i in range(26):\n",
    "            if color[i] is None:\n",
    "                t+=1\n",
    "                stack=[i]\n",
    "                while stack:\n",
    "                    node=stack.pop()\n",
    "                    for nei in graph[node]:\n",
    "                        if color[nei] is None:\n",
    "                            color[nei]=t\n",
    "                            stack.append(nei)\n",
    "        for i in equations:\n",
    "            if i[1]=='!':\n",
    "                x=ord(i[0])-ord('a')\n",
    "                y=ord(i[3])-ord('a')\n",
    "                if x==y:return False\n",
    "                if color[x] is not None and color[x]==color[y]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        p = list(range(27))\n",
    "\n",
    "        def get_root(x):\n",
    "            if p[x] != p[p[x]]:\n",
    "                p[x] = get_root(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        for s in equations:\n",
    "            if s[1] == \"=\":\n",
    "                left_root = get_root(ord(s[0]) - 97)\n",
    "                right_root = get_root(ord(s[3]) - 97)\n",
    "                left_root, right_root = (left_root, right_root) if right_root > left_root else (right_root, left_root)\n",
    "                if left_root != right_root:\n",
    "                    p[right_root] = left_root\n",
    "\n",
    "        for s in equations:\n",
    "            if s[1] == \"!\":\n",
    "                left_root = get_root(ord(s[0]) - 97)\n",
    "                right_root = get_root(ord(s[3]) - 97)\n",
    "                if left_root == right_root:\n",
    "                    return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind(object):\n",
    "    def __init__(self, n):\n",
    "        self.size = [1]*n\n",
    "        self.parent = [0]*n\n",
    "        self.count = n\n",
    "        for i in range(n):\n",
    "            self.parent[i] = i\n",
    "            \n",
    "    def find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "        \n",
    "    def uinon(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "        if self.size[rootP] > self.size[rootQ]:\n",
    "            self.parent[rootQ] = rootP\n",
    "            self.size[rootP] += self.size[rootQ]\n",
    "        else:\n",
    "            self.parent[rootP] = rootQ\n",
    "            self.size[rootQ] += self.size[rootP]\n",
    "        self.count -= 1\n",
    "        \n",
    "    def isConnected(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        return rootP == rootQ\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        u = UnionFind(26)\n",
    "        for equ in equations:\n",
    "            first, equal, end = equ[0], equ[1:-1] == \"==\", equ[-1]\n",
    "            if equal:\n",
    "                u.uinon(ord(first)-ord(\"a\"), ord(end)-ord(\"a\"))\n",
    "        for equ in equations:\n",
    "            first, equal, end = equ[0], equ[1:-1] == \"==\", equ[-1]\n",
    "            if not equal:\n",
    "                if u.isConnected(ord(first)-ord(\"a\"), ord(end)-ord(\"a\")):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        f = {}\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            while x != f[x]:\n",
    "                x = f[x]\n",
    "            return x\n",
    "\n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "        stack = []\n",
    "        for idx,e in enumerate(equations):\n",
    "            if e[1] == '=':\n",
    "                union(e[0], e[3])\n",
    "            else:\n",
    "                stack.append(idx)\n",
    "\n",
    "        for i in stack:\n",
    "            if find(equations[i][0]) == find(equations[i][3]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, N: int) -> None:\n",
    "        self._fa = list(range(N))\n",
    "        self._size = [1] * N\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x != self._fa[x]:\n",
    "            self._fa[x] = self.find(self._fa[x])\n",
    "        return self._fa[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self._size[x] < self._size[y]:\n",
    "            x, y = y, x\n",
    "        self._fa[y] = x\n",
    "        self._size[x] += self._size[y]\n",
    "\n",
    "    @property\n",
    "    def fa(self):\n",
    "        return self._fa\n",
    "\n",
    "    @property\n",
    "    def groups(self):\n",
    "        return sum(1 for i, x in enumerate(self._fa) if i == x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        uf = UnionFind(26)\n",
    "        for a, _, _, b in filter(lambda eq: eq[1] == \"=\", equations):\n",
    "            x, y = ord(a) - 97, ord(b) - 97\n",
    "            uf.union(x, y)\n",
    "        for a, _, _, b in filter(lambda eq: eq[1] == \"!\", equations):\n",
    "            x, y = ord(a) - 97, ord(b) - 97\n",
    "            if uf.find(x) == uf.find(y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 990. 等式方程的可满足性\n",
    "# 思路：并查集 将相等的变量 纳入 相同的集合， 不相等的变量不能属于同一个集合\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        if not equations: return True\n",
    "        father = {}\n",
    "\n",
    "        def get_father(x):\n",
    "            nonlocal father\n",
    "            if x in father:\n",
    "                if x == father[x]:\n",
    "                    return x\n",
    "                else:\n",
    "                    father[x] = get_father(father[x])\n",
    "                    return father[x]\n",
    "            else:\n",
    "                father[x] = x\n",
    "                return x\n",
    "\n",
    "        def union(x, y):\n",
    "            nonlocal father\n",
    "            x_f = get_father(x)\n",
    "            y_f = get_father(y)\n",
    "            father[x_f] = y_f\n",
    "\n",
    "        def is_same(x, y):\n",
    "            return get_father(x) == get_father(y)\n",
    "\n",
    "        o_ls = []\n",
    "        for val in equations:\n",
    "            if val[1] == \"=\":\n",
    "                union(val[0], val[3])\n",
    "            else:\n",
    "                o_ls.append(val)\n",
    "\n",
    "        for val in o_ls:\n",
    "            if is_same(val[0], val[3]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        class UnionFind:\n",
    "            def __init__(self, n):\n",
    "                self.parent = [i for i in range(n)]\n",
    "\n",
    "            def find(self, x):  # 隔代压缩，找到 x 的代表节点\n",
    "                while x != self.parent[x]:\n",
    "                    self.parent[x] = self.parent[self.parent[x]]\n",
    "                    x = self.parent[x]\n",
    "                return x\n",
    "\n",
    "            def union(self, x, y):     # 合并 x 和 y 节点\n",
    "                root_x = self.find(x)  # 找到 x 的代表节点 \n",
    "                root_y = self.find(y)  # 找到 y 的代表节点\n",
    "                self.parent[root_x] = root_y  # 代表节点的合并\n",
    "\n",
    "            def is_connected(self, x, y):    # 查看x和y是否相连 \n",
    "                return self.find(x) == self.find(y)  # 判断x和y的代表节点是否相同\n",
    "\n",
    "        unionFind = UnionFind(26)   # 26个字母的并查集\n",
    "        # 一个方程有四个字符，只需要判断第一个和第四个字符\n",
    "        # 判断等式方程\n",
    "        for equation in equations:\n",
    "            if equation[1] == '=':\n",
    "                index1 = ord(equation[0]) - ord('a')  # 第一个字符\n",
    "                index2 = ord(equation[3]) - ord('a')  # 最后一个字符\n",
    "                unionFind.union(index1, index2)  # 合并这两个字符\n",
    "\n",
    "        # 判断不等式方程 \n",
    "        for equation in equations:\n",
    "            if equation[1] == '!':\n",
    "                index1 = ord(equation[0]) - ord('a')   # 第一个字符\n",
    "                index2 = ord(equation[3]) - ord('a')   # 最后一个字符\n",
    "                if (unionFind.is_connected(index1, index2)): # 判断这两个字符是否相连 \n",
    "                    return False   \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        graph = defaultdict(set)\n",
    "        elements = []\n",
    "        for eq in equations:\n",
    "            u = eq[0]\n",
    "            v = eq[-1]\n",
    "            elements += [u,v]\n",
    "            if eq[1]==\"=\":\n",
    "                graph[u].add(v)\n",
    "                graph[v].add(u)\n",
    "            else:\n",
    "                graph[u].add(v+\"_n\")\n",
    "                graph[v].add(u+\"_n\")\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            for neighbour in graph[node]:\n",
    "                if neighbour not in visited:\n",
    "                    dfs(neighbour)\n",
    "                    \n",
    "        for i in elements:\n",
    "            visited.clear()\n",
    "            dfs(i)\n",
    "            if i+\"_n\" in visited:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        def find(x):\n",
    "            if x == p[x]:\n",
    "                return p[x]\n",
    "            else:\n",
    "                p[x] = find(p[x])\n",
    "                return p[x]\n",
    "        \n",
    "        #----------------union find------------------\n",
    "        p = [i for i in range(500)]\n",
    "        # '=='\n",
    "        for eq in equations:\n",
    "            if eq[1] == '=':\n",
    "                r1 = find(ord(eq[0]) - ord('a'))        \n",
    "                r2 = find(ord(eq[3]) - ord('a'))\n",
    "                if r1!= r2:\n",
    "                    p[r2] = r1\n",
    "        \n",
    "        # '!='\n",
    "        for eq in equations:\n",
    "            if eq[1] == '!':\n",
    "                r1 = find(ord(eq[0]) - ord('a'))        \n",
    "                r2 = find(ord(eq[3]) - ord('a'))\n",
    "                if r1== r2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        parents = {}\n",
    "        def find(c):\n",
    "            if c not in parents:\n",
    "                parents[c] = c\n",
    "\n",
    "            p = parents[c]\n",
    "            while p != parents[p]:\n",
    "                p = parents[p]\n",
    "            parents[c] = p\n",
    "            return p\n",
    "        \n",
    "        def union(a,b):\n",
    "            pa = find(a)\n",
    "            pb = find(b)\n",
    "            if pa != pb:\n",
    "                parents[pa] = pb\n",
    "        v = 0\n",
    "        for e in equations:\n",
    "            a = e[0]\n",
    "            b = e[-1]\n",
    "            if e[1] == '=':\n",
    "                union(a,b)\n",
    "        for e in equations:\n",
    "            a = e[0]\n",
    "            b = e[-1]\n",
    "            if e[1] == '!':\n",
    "                pa = find(a)\n",
    "                pb = find(b)\n",
    "                #print(pa, pb, parents)\n",
    "                if pa == pb:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        uf = UnionFind(26)\n",
    "        for e in equations:\n",
    "            if e[1] == \"=\":\n",
    "                uf.union(ord(e[0]) - 97, ord(e[-1]) - 97)\n",
    "        for e in equations:\n",
    "            if e[1] != \"=\":\n",
    "                if uf.connected(ord(e[0]) - 97, ord(e[-1]) - 97):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "class UnionFind():\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "\n",
    "    def find(self, p):\n",
    "        if self.parents[p] != p:\n",
    "            self.parents[p] = self.find(self.parents[p])\n",
    "        return self.parents[p]\n",
    "\n",
    "\n",
    "    def union(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "        self.parents[rootQ] = rootP\n",
    "        self.count -= 1\n",
    "\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.parent = []\n",
    "        self.children_size = []\n",
    "\n",
    "    def find_parent(self, val):\n",
    "        while self.parent[val] != val:\n",
    "            val = self.parent[val]\n",
    "        return val\n",
    "\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        self.parent = [i for i in range(26)]\n",
    "        self.children_size = [0] * 26\n",
    "        for val in equations:\n",
    "            if val[1] == \"=\":\n",
    "                left = ord(val[0]) - ord('a')\n",
    "                left_parent = self.find_parent(left)\n",
    "                right = ord(val[-1]) - ord('a')\n",
    "                right_parent = self.find_parent(right)\n",
    "                if left_parent == right_parent:\n",
    "                    continue\n",
    "                if self.children_size[left_parent] < self.children_size[right_parent]:\n",
    "                    self.parent[left_parent] = right_parent\n",
    "                    self.children_size[right_parent] += 1\n",
    "                else:\n",
    "                    self.parent[right_parent] = left_parent\n",
    "                    self.children_size[left_parent] += 1\n",
    "\n",
    "        for val in equations:\n",
    "            if val[1] == \"!\":\n",
    "                left = ord(val[0]) - ord('a')\n",
    "                left_parent = self.find_parent(left)\n",
    "                right = ord(val[-1]) - ord('a')\n",
    "                right_parent = self.find_parent(right)\n",
    "                if left_parent == right_parent:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        roots = {}\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                roots[rx] = ry\n",
    "        def check(x, y):\n",
    "            return find(x) == find(y)\n",
    "        def add(x):\n",
    "            if x not in roots:\n",
    "                roots[x] = x\n",
    "        \n",
    "        for x, sig, _ , y in sorted(equations, key = lambda x:x[1] == '!'): # ！放后面判断\n",
    "            add(x)\n",
    "            add(y)\n",
    "            if sig == '!' and check(x, y):\n",
    "                return False\n",
    "            elif sig == '=': # 不能直接else\n",
    "                union(x, y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        class UnionFind():\n",
    "            def __init__(self,n):\n",
    "                self.p=list(range(n))\n",
    "                print(self.p)\n",
    "            def find(self,x):\n",
    "                if self.p[x]!=x:\n",
    "                    self.p[x]=self.find(self.p[x])\n",
    "                return self.p[x]\n",
    "            def union(self,x,y):\n",
    "                x=self.find(x)\n",
    "                y=self.find(y)\n",
    "                self.p[x]=self.find(y)\n",
    "            def is_connect(self,x,y):\n",
    "                return self.find(x)==self.find(y)\n",
    "        uf=UnionFind(26)\n",
    "        for equation in equations:\n",
    "            if equation[1]==\"=\":\n",
    "                x=ord(equation[0])-ord('a')\n",
    "                y=ord(equation[3])-ord('a')\n",
    "                uf.union(x,y)\n",
    "        for equation in equations:\n",
    "            if equation[1]==\"!\":\n",
    "                x=ord(equation[0])-ord('a')\n",
    "                y=ord(equation[3])-ord('a')\n",
    "                if uf.is_connect(x,y):\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        uf = [i for i in range(len(equations) * 2)]\n",
    "        map = {}\n",
    "        count = 0\n",
    "        for e in equations:\n",
    "            a = e[0]\n",
    "            b = e[-1]\n",
    "            if map.get(a) == None:\n",
    "                map[a] = count\n",
    "                count += 1\n",
    "            if map.get(b) == None:\n",
    "                map[b] = count\n",
    "                count += 1\n",
    "\n",
    "        def find(x):\n",
    "            if x != uf[x]:\n",
    "                uf[x] = find(uf[x])\n",
    "            return uf[x]\n",
    "        \n",
    "        for e in equations:\n",
    "            a = e[0]\n",
    "            sign = e[1:3]\n",
    "            b = e[-1]\n",
    "            if sign == \"==\":\n",
    "                ra = find(map[a])\n",
    "                rb = find(map[b])\n",
    "                if ra != rb:\n",
    "                    uf[ra] = rb\n",
    "        for e in equations:\n",
    "            a = e[0]\n",
    "            sign = e[1:3]\n",
    "            b = e[-1]\n",
    "            if sign == \"!=\":\n",
    "                ra = find(map[a])\n",
    "                rb = find(map[b])\n",
    "                if ra == rb:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        # 并查集 先把所有相等的union 然后根据!判断\n",
    "        uf = UF(26)\n",
    "        for equation in equations:\n",
    "            x, y = ord(equation[0])-97, ord(equation[3])-97\n",
    "            isequals = equation[1]\n",
    "            if isequals == '=':\n",
    "                uf.union(x, y)\n",
    "\n",
    "        for equation in equations:\n",
    "            x, y = ord(equation[0])-97, ord(equation[3])-97\n",
    "            isequals = equation[1]\n",
    "            if isequals == '!':\n",
    "                if uf.connected(x, y):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [0] * n\n",
    "        for i in range(n):\n",
    "            self.parent[i] = i \n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return\n",
    "        self.parent[rootY] = rootX \n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    class UnionFind:\n",
    "        def __init__(self):\n",
    "            self.parent = list(range(26))\n",
    "        \n",
    "        def find(self, index):\n",
    "            if index == self.parent[index]:\n",
    "                return index\n",
    "            self.parent[index] = self.find(self.parent[index])\n",
    "            return self.parent[index]\n",
    "        \n",
    "        def union(self, index1, index2):\n",
    "            self.parent[self.find(index1)] = self.find(index2)\n",
    "\n",
    "\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        uf = Solution.UnionFind()\n",
    "        for st in equations:\n",
    "            if st[1] == \"=\":\n",
    "                index1 = ord(st[0]) - ord(\"a\")\n",
    "                index2 = ord(st[3]) - ord(\"a\")\n",
    "                uf.union(index1, index2)\n",
    "        for st in equations:\n",
    "            if st[1] == \"!\":\n",
    "                index1 = ord(st[0]) - ord(\"a\")\n",
    "                index2 = ord(st[3]) - ord(\"a\")\n",
    "                if uf.find(index1) == uf.find(index2):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.states = [i for i in range(n)]\n",
    "    def find(self, i):\n",
    "        if self.states[i] != i: self.states[i] = self.find(self.states[i])\n",
    "        return self.states[i]\n",
    "    def union(self, i, j):\n",
    "        self.states[self.find(i)] = self.find(j)\n",
    "\n",
    "class Solution:\n",
    "    def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        ls = set()\n",
    "        for eq in equations:\n",
    "            ls.add(eq[0])\n",
    "            ls.add(eq[3])\n",
    "        pos, n = {l: i for i, l in enumerate(ls)}, len(ls)\n",
    "        dsu = DSU(n)\n",
    "        for eq in equations:\n",
    "            i1, i2 = pos[eq[0]], pos[eq[3]]\n",
    "            if eq[1] == '=': dsu.union(i1, i2)\n",
    "        for eq in equations:\n",
    "            i1, i2 = pos[eq[0]], pos[eq[3]]\n",
    "            if eq[1] == '!' and dsu.find(i1) == dsu.find(i2): return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
